416. Partition Equal Subset Sum
Medium

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

 

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

 

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
Accepted
296,756
Submissions
656,408
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.75 (67 votes)

Premium

Video Solution


 

Solution Article


Overview

The problem is similar to the classic Knapsack problem. The basic idea is to understand that to partition an array into two subsets of equal sum say subSetSum\text{subSetSum}, the totalSum\text{totalSum} of given array must be twice the subSetSum\text{subSetSum}

totalSum=subSetSum2\text{totalSum} = \text{subSetSum} * 2

This could also be written as, subSetSum=totalSum/2\text{subSetSum} = \text{totalSum}/2

Example Assume totalSum\text{totalSum} of an array is 2020 and if we want to partition it into 2 subsets of equal sum, then the subSetSum\text{subSetSum} must be (20/2)=10(20/2) = 10.

Now, the problem to find the subset with a sum equals a given target. Here target is subSetSum\text{subSetSum}.

It must be noted that the total sum of an array must be even, only then we can divide it into 2 equal subsets. For instance, we cannot have an equal subSetSum\text{subSetSum} for an array with total sum as 2121.

Note:

Finding a subset with a sum equal to a given target is different than Subarray sum equals k. Subarray is a contiguous sequence of array elements, whereas the subset could consist of any array elements regardless of the sequence. But each array element must belong to exactly one subset.

Let's discuss different algorithms to find the subset with a given sum.


Approach 1: Brute Force

Intuition

We have to find a subset in an array where the sum must be equal to subSetSum\text{subSetSum} that we calculated above. The brute force approach would be to generate all the possible subsets of an array and return true if we find a subset with the required sum.

Algorithm

Assume, there is an array nums\text{nums} of size nn and we have to find if there exists a subset with total sum=subSetSum\text{sum} = \text{subSetSum}. For a given array element xx, there could be either of 2 possibilities:

  • Case 1) xx is included in subset sum. subSetSum=subSetSumx\text{subSetSum} = \text{subSetSum} - x

  • Case 2) xx is not included in subset sum, so we must take previous sum without xx. subSetSum=subSetSum\text{subSetSum} = \text{subSetSum}

We can use depth first search and recursively calculate the subSetSum\text{subSetSum} for each case and check if either of them is true. This can be formulated as

isSum (subSetSum, n) = isSum(subSetSum- nums[n], n-1) ||  isSum(subSetSum, n-1)

Base Cases

  • If subSetSum\text{subSetSum} is 00, return true ( Since we found a subset with sum subSetSum )
  • If subSetSum\text{subSetSum} is less than 00, return false

Complexity Analysis

  • Time Complexity : O(2n)\mathcal{O}(2^{n}), where nn is equal to number of array elements. The recursive solution takes the form of a binary tree where there are 2 possibilities for every array element and the maximum depth of the tree could be nn. The time complexity is exponential, hence this approach is exhaustive and results in Time Limit Exceeded (TLE).

  • Space Complexity: O(N)\mathcal{O}(N) This space will be used to store the recursion stack. We can’t have more than nn recursive calls on the call stack at any time.


Approach 2: Top Down Dynamic Programming - Memoization

Intuition

In the above approach, we observe that the same subproblem is computed and solved multiple times.

Example :

img

In the above recursion tree, we could see that isSum(3,[6])\text{isSum}( 3,[6] ) is computed twice and the result is always the same. Since the same subproblem is computed again and again, the problem has Overlapping Subproblem property and can be solved using Dynamic Programming.

Algorithm

We could have stored the results of our computation for the first time and used it later. This technique of computing once and returning the stored value is called memoization. We use a two dimensional array memo\text{memo} and follow the following steps for each recursive call :

  • Check if subSetSum for a given nn exists in memo\text{memo} to see if we can avoid computing the answer and return the result stored in memo.
  • Save the results of any calculations to memo\text{memo}.

Complexity Analysis

Let nn be the number of array elements and mm be the subSetSum\text{subSetSum}.

  • Time Complexity : O(mn)\mathcal{O}(m \cdot n).

    • In the worst case where there is no overlapping calculation, the maximum number of entries in the memo would be mnm \cdot n. For each entry, overall we could consider that it takes constant time, i.e. each invocation of dfs() at most emits one entry in the memo.

    • The overall computation is proportional to the number of entries in memo. Hence, the overall time complexity is O(mn)\mathcal{O}(m \cdot n).

  • Space Complexity: O(mn)\mathcal{O}(m \cdot n). We are using a 2 dimensional array memo\text{memo} of size (mn)(m \cdot n) and O(n)\mathcal{O}(n) space to store the recursive call stack. This gives us the space complexity as O(n)\mathcal{O}(n) + O(mn)\mathcal{O}(m \cdot n) = O(mn)\mathcal{O}(m \cdot n)


Approach 3: Bottom Up Dynamic Programming

Intuition

This is another approach to solving the Dynamic Programming problems. We use the iterative approach and store the result of subproblems in bottom-up fashion also known as Tabulation.

Algorithm

We maintain a 2D array , dp[n][subSetSum]\text{dp}[n][\text{subSetSum}] For an array element ii and sum jj in array nums\text{nums},

dp[i][j]=true\text{dp}[i][j] = \text{true} if the sum jj can be formed by array elements in subset nums[0]..nums[i]\text{nums[0]} .. \text{nums[i]},otherwise dp[i][j]=false\text{dp}[i][j] = \text{false}

dp[i][j]\text{dp}[i][j] is true\text{true} it satisfies one of the following conditions :

  • Case 1) sum jj can be formed without including ithi^{th} element,

if dp[i1][j]==true\text{if } \text{dp}[i-1][j] == \text{true}

  • Case 2) sum jj can be formed including ithi^{th} element,

if dp[i1][jnums[i]]==true\text{if } \text{dp}[i-1][j - \text{nums}[i]] == \text{true}

Current
1 / 10

Complexity Analysis

  • Time Complexity : O(mn)\mathcal{O}(m \cdot n), where mm is the subSetSum\text{subSetSum}, and nn is the number of array elements. We iteratively fill the array of size mnm \cdot n.

  • Space Complexity : O(mn)\mathcal{O}(m \cdot n) , where nn is the number of array elements and mm is the subSetSum\text{subSetSum}. We are using a 2 dimensional array dp\text{dp} of size mnm \cdot n


Approach 4: Optimised Dynamic Programming - Using 1D Array

Intuition

We could further optimize Approach 3. We must understand that for any array element ii, we need results of the previous iteration (i-1) only. Hence, we could achieve the same using a one-dimensional array as well.

Complexity Analysis

  • Time Complexity : O(mn)\mathcal{O}(m \cdot n), where mm is the subSetSum\text{subSetSum}, and nn is the number of array elements. The time complexity is the same as Approach 3.

  • Space Complexity: O(m)\mathcal{O}(m), As we use an array of size mm to store the result of subproblems.

Note:

The overall performance of Approach 2 is better than all the approaches discussed above. This is because we terminate our search as soon as we find a subset with the required sum. Hence, it performs better in most cases except for the worst case.

Report Article Issue

Comments: 34
calmhandtitan's avatar
Read More

Why iterate from back in Approach 4? iterating from starting is giving WA
for (int j = subSetSum; j >= curr; j--)

10
Show 5 replies
Reply
Share
Report
Shradha1994's avatar
Read More

Due to nature of this problem, it is possible that there are no overlapping subproblems as well. Example, when all the numbers are odd. [7,5,3,1], sum = 16, subset sum = 8. The recursion tree would be
image
It is evident that none of the subproblems overlap.
In such cases the memoization approach (Approach 2) would have same time complexity as Approach 1.
@caitao @dev_ps @rexhu100

14
Show 2 replies
Reply
Share
Report
rexhu100's avatar
Read More

The memoization approach should have the same time complexity as the bottom-up DP approach.

15
Show 10 replies
Reply
Share
Report
cailucun's avatar
Read More

Can anyone explain in Solution 2, why do we only use subSetSum as the key of the memo?

I think it should be a pair of (subSetSum, n).

The solution doesn't work when I switch the order of

boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1]) || dfs(nums, n - 1, subSetSum);

to

boolean result = dfs(nums, n - 1, subSetSum) || dfs(nums, n - 1, subSetSum - nums[n - 1]);

9
Show 6 replies
Reply
Share
Report
dklearner's avatar
Read More

Well explained!!!. I have one doubt though
Why we are subtracting nums[n-1] here?
boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1], memo) ||
dfs(nums, n - 1, subSetSum, memo);
According to the recursion equation, recursive call should be like this
boolean result = dfs(nums, n - 1, subSetSum - nums[n], memo) ||
dfs(nums, n - 1, subSetSum, memo); // since we are calling the function with index n-1.
Since we are deducting the value at n-1th index, I am wondering how this solution is working for not considering the current value which is at index 'n'?

4
Show 1 reply
Reply
Share
Report
l333tcoder's avatar
Read More

In approach 1 and 2, the code for recurrence calls is not correct for the subsetSum problem in general (where the target may be any number).
It never takes nums[n-1] into consideration while calculating the subset sum.
First input to dfs() is newN=n-1. Then, nums[newN-1] (=n-1-1 =n-2) is subtracted from subSetSum.

It happens to works for this problem since the target is sum/2.
In this problem, there must be 0 or 2 subsets with the same sum as target (total sum = target+target).
So even if the subset containing nums[n-1] is missed, the other subset is found and it will return true.

4
Reply
Share
Report
plottwist's avatar
Read More

The new video Leetcode provides explains everything clearly and concisely. This is an awesome addition and hopefully we can see this kind of solution more.

3
Reply
Share
Report
marcello834's avatar
Read More

"The problem is similar to the classic Knapsack problem": I don't get it...

4
Show 3 replies
Reply
Share
Report
arctdav's avatar
Read More

This is the python3 version of approach 3

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        totalSum = sum(nums)
        if totalSum % 2 != 0: return False
        subSetSum = totalSum // 2
        n = len(nums)
        dp = [[False] * (subSetSum+1) for _ in range(n+1)]
        dp[0][0] = True
        for i in range(1, n+1):
            curr = nums[i-1]
            for j in range(subSetSum+1):
                if j < curr:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-curr]
        return dp[n][subSetSum]

2
Show 1 reply
Reply
Share
Report
ltbtb_rise's avatar
Read More

I don't understand why the memoization is in this form: unordered_map<int, bool> memo;

the recursion function is getting called with a specific index and subsetSum: bool dfs(vector<int> &nums, int n, int subSetSum)

So why the memoization memo does not need to be associated with an index at all? I am really confused about this.

2
Show 1 reply
Reply
Share
Report
Success
Details
Runtime: 252 ms, faster than 27.96% of C++ online submissions for Partition Equal Subset Sum.
Memory Usage: 11.8 MB, less than 54.07% of C++ online submissions for Partition Equal Subset Sum.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/18/2021 19:49Accepted252 ms11.8 MBcpp
06/18/2021 19:47Accepted300 ms75.9 MBcpp
03/27/2021 08:26Accepted96 ms11.2 MBcpp
03/16/2021 13:50Accepted96 ms11.3 MBcpp
08/29/2020 16:33Accepted60 ms9.5 MBcpp
08/29/2020 16:32Accepted56 ms9.6 MBcpp
08/29/2020 16:32Wrong AnswerN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.